package org.lep.leetcode.datastructure.heap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 *
 * @author lverpeng
 * @since 2020/3/10
 */
public class SlidingWindowMax {
    /**
     * 队列中保持最左边最大
     * 维护：每次拿队列最右边的值a和下一个值b比较，如果a < b说明a需要移出队列，
     * 循环比较下一个最右值a1和b的关系，直到队列为空或者找到一个值大于b，这样就能保证队列的最左边一直是最大的
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length
                == 0) {
            return nums;
        }
        int[] result = new int[nums.length - k + 1];
        int count = 0;
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i > k - 1 && queue.peek() <= i - k) {
                queue.poll();
            }
            while (!queue.isEmpty() && nums[queue.getLast()] < nums[i]) {
                queue.pollLast();
            }
            queue.offer(i);
            if (i >= k - 1) {
                result[count++] = nums[queue.peek()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        SlidingWindowMax slidingWindowMax = new SlidingWindowMax();
        System.out.println(Arrays.toString(slidingWindowMax.maxSlidingWindow(new int[]{1,3,1,2,0,5}, 3)));
        System.out.println(Arrays.toString(slidingWindowMax.maxSlidingWindow(new int[]{1,3,1,0,0,5}, 3)));
        System.out.println(Arrays.toString(slidingWindowMax.maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3)));
        System.out.println(Arrays.toString(slidingWindowMax.maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 1)));
        System.out.println(Arrays.toString(slidingWindowMax.maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 8)));
        System.out.println(Arrays.toString(slidingWindowMax.maxSlidingWindow(new int[]{7,2,4}, 2)));
    }
}
